/*
 * @lc app=leetcode.cn id=417 lang=cpp
 *
 * [417] 太平洋大西洋水流问题
 */

// @lc code=start
class Solution
{
public:
    struct Point
    {
        int x, y, type;
        Point(int x, int y, int type) : x(x), y(y), type(type) {}
    };
    int visited[205][205] = {0};
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights)
    {
        int m = heights.size(), n = heights[0].size();
        vector<vector<int>> ans;
        queue<Point> q;
        for (int i = 0; i < m; i++)
        {
            q.push(Point(i, 0, 1));
            visited[i][0] |= 1;
            q.push(Point(i, n - 1, 2));
            visited[i][n - 1] |= 2;
        }
        for (int j = 0; j < n; j++)
        {
            q.push(Point(0, j, 1));
            visited[0][j] |= 1;
            q.push(Point(m - 1, j, 2));
            visited[m - 1][j] |= 2;
        }

        while (!q.empty())
        {
            Point curr = q.front();
            q.pop();
            // 向四个方向搜索
            for (auto [dx, dy] : dirs)
            {
                int x = curr.x + dx, y = curr.y + dy;
                if (x < 0 || x >= m || y < 0 || y >= n || (visited[x][y] & curr.type) != 0)
                {
                    continue;
                }
                if (heights[x][y] < heights[curr.x][curr.y])
                {
                    continue;
                }
                visited[x][y] |= curr.type;
                q.push(Point(x, y, curr.type));
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (visited[i][j] == 3)
                {
                    ans.push_back({i, j});
                }
            }
        }
        return ans;
    }
};
// @lc code=end
